#include <stdio.h>

#define N 5
/**
 * File: Exercise1019.c
 * -------------------------------------------------------
 * 1.19 Give an example showing that modifying quick union (Program 1.2) to implement full path compression (see Exercise 1.16)
 * is not sufficient to ensure that the trees have no long paths.
 * -------------------------------------------------------
 * 编译
 * gcc -o Exercise1019 Exercise1019.c
 * -----------------------------------------------------
 * 运行
 * ./Exercise1019
 * 0 1 1 2 2 3 3 4
 *
 */
int main(int argc, char **argv){
    int i, p, q, j, root;
    int id[N];

    for (i = 0; i < N; i++) {
        id[i] = i;
    }

    while (scanf("%d %d\n", &p, &q) == 2) {
        for (i = p; i != id[i]; i = id[i]) {
            ;
        }
        root = i;
        for (i = p; i != id[i]; i = id[i]) {
            id[i] = root;
        }

        for (j = q; j != id[j]; j = id[j]) {
            ;
        }
        root = j;
        for (j = q; j != id[j]; j = id[j]) {
            id[j] = root;
        }

        if (i == j) {
            continue;
        }
        id[i] = j;//让对象i指向j
        printf("%d %d\n", p, q);
    }
    return 0;
}